//
// Created by Administrator on 2021/11/4.
// May Saint Diana bless you!
//
#include <vector>
#include <iostream>


using namespace std;

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;

    /**
     * 1~n 选出k个进行组合
     * @param n
     * @param k
     * @return
     */
    vector<vector<int>> combine(int n, int k) {
        backtrack(1, n, k);
        return ans;
    }

    void backtrack(int cur, int n, int k) {
        // 剩下的不够
        if (temp.size() + n - cur + 1 < k)
            return;
        // 记录合法的
        if (temp.size() == k) {
            ans.push_back(temp);
            return;
        }
        // 当前位置的数，可以加入，可以不加入
        temp.push_back(cur);
        backtrack(cur + 1, n, k);
        temp.pop_back();
        backtrack(cur + 1, n, k);
    }
};

int main() {
    Solution solution;
    vector<vector<int>>ans = solution.combine(5,2);
    for(const vector<int>&row:ans){
        for(const int &x:row){
            cout << x <<" ";
        }
        cout << endl;
    }
    return 0;
}
